import java.util.ArrayList;
import java.util.List;

public class 螺旋矩阵 {

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int n = matrix.length;
        int m = matrix[0].length;
        int up = 0;
        int down = n;
        int left = 0;
        int right = m;
        int i = 0;
        int j = 0;
        while (up < down && left < right) {

            for (;j < right;j++) {
                ans.add(matrix[i][j]);
            }
            i++; // 防止重复遍历
            j--; // 多加了一次回退
            up++; // 这一层不再遍历
            for (;i < down;i++) {
                ans.add(matrix[i][j]);
            }
            j--; // 防止重复遍历
            i--; // 多加一次回退
            right--;

            for (;j >= left;j--) {
                ans.add(matrix[i][j]);
            }
            i--; // 防止重复遍历
            j++; // 多加了一次回退
            down--;
            for (;i >= up;i--) {
                ans.add(matrix[i][j]);
            }
            i++;
            j++;
            left++;

        }
        int cnt = ans.size() - n * m;
        while (cnt-- > 0) {
            ans.remove(ans.size() - 1);
        }
        return ans;
    }
}
